#include <bits/stdc++.h>

using namespace std;

void printVector(vector<int> v)
{
    for(int i = 0; i < v.size(); i++)
        printf("%d\t", v[i]);
    printf("\n");
}

vector<int> maxSlidingWindow(vector<int> nums, int k)
{
    // write your code here
    if(nums.empty() || k <= 1)
        return nums;
    int max = nums[0], index = 0;//当前窗口里最大的元素及对应的位置
    vector<int> maxs;
    if(nums.size() <= k)
    {
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] >= max)
            {
                max = nums[i];
            }
        }
        maxs.push_back(max);
    }
    else
    {
//        for(int i = 0; i <= nums.size() - k; i++)
//        {
//            max = nums[i];
//            for(int j = i; j < i + k; j++)
//            {
//                if(nums[j] >= max)
//                {
//                    max = nums[j];
//                }
//            }
//            maxs.push_back(max);
//        }
        //部分改进（提升有限）：两种情况:max被滑动出去了，需要重新计算；max没被滑动出去，只需比较max跟新加入即可
        for(int i = 0; i < k; i++)
        {
            if(nums[i] >= max)
            {
                max = nums[i];
                index = i;
            }
        }
        printf("0:%d %d\n", max, index);
        maxs.push_back(max);
        for(int i = k; i < nums.size(); i++)
        {
            if(index != i - k) //max没被滑动出去了
            {
                if(nums[i] >= max)
                {
                    max = nums[i];
                    index = i;
                }
                printf("1:%d %d\n", max, index);
            }
            else
            {
                max = nums[i];
                index = i;
                for(int j = i - k + 1; j <= i; j++)
                {
                    if(nums[j] >= max)
                    {
                        max = nums[j];
                        index = j;
                    }
                }
                printf("2:%d %d\n", max, index);
            }
            maxs.push_back(max);
        }
    }
    return maxs;
}

int main()
{
    vector<int> v;
    v = {1,2,7,7,2};
    v = {1,2,7,7,2,10,3,4,5};
//    v = {1,2,7,7,8,4,5,5,2,1,2,4,5,20,3};
//    for(int i = 0; i < 100; i++)
//        v.push_back(rand());
    printVector(v);
    printVector(maxSlidingWindow(v, 2));
    return 0;
}

/**
 362. 滑动窗口的最大值

给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

样例

给出数组 [1,2,7,7,8], 滑动窗口大小为 k = 3. 返回 [7,7,8].

解释：

最开始，窗口的状态如下：

[|1, 2 ,7| ,7 , 8], 最大值为 7;

然后窗口向右移动一位：

[1, |2, 7, 7|, 8], 最大值为 7;

最后窗口再向右移动一位：

[1, 2, |7, 7, 8|], 最大值为 8.
*/
